package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Description MergeSort
 * @Author wanghaiwei
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] input = new int[]{21, 2, 4, 19, 33, 1, 7, 9, 2, 4};
        ArrayUtils.shuffle(input);
        System.out.println("mergeSort排序前：" + Arrays.toString(input));
        mergeSort(input, 0, input.length - 1);
        System.out.println("mergeSort排序后：" + Arrays.toString(input));
    }

    /**
     * 参考文章：https://leetcode.cn/circle/article/zeM9YK/
     *
     * @param input
     * @param leftIdx
     * @param rightIdx
     */
    public static void mergeSort(int[] input, int leftIdx, int rightIdx) {
        if (leftIdx >= rightIdx) {
            //此时说明已经只剩一个元素了，不需要拆分了
            return;
        }
        int midIdx = (leftIdx + rightIdx) / 2;
        //左区间递归
        mergeSort(input, leftIdx, midIdx);
        //有区间递归
        mergeSort(input, midIdx + 1, rightIdx);
        //向上合并过程
        //临时数组，用来保存合并的临时结果
        int[] tmp = new int[rightIdx - leftIdx + 1];
        int i = leftIdx; //左区间指针
        int j = midIdx + 1; //右区间指针
        for (int tmpIdx = 0; tmpIdx < (rightIdx - leftIdx + 1); tmpIdx++) {
            if (i == midIdx + 1) { //此时表示左区间已经结束,将右区间剩余数据依次放进结果即可
                tmp[tmpIdx] = input[j++];
            } else if (j == rightIdx + 1) {//此时表示右区间已经结束,将左区间剩余数据依次放进结果即可
                tmp[tmpIdx] = input[i++];
            } else if (input[i] <= input[j]) { //此时两个区间都未结束，所以比较双方当前的值，较小值放入临时结果，并且小的一方，指针移动到下一个位置
                tmp[tmpIdx] = input[i++];
            } else {
                tmp[tmpIdx] = input[j++];
            }
        }
        //临时结果，需要覆盖掉原始的数组
        for (int k = leftIdx; k <= rightIdx; k++) {
            input[k] = tmp[k - leftIdx];
        }
    }
}
